package com.itdfq.LeetCode.leetcode.editor.cn;
//给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位数字。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：n = 11
//输出：0
//解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
// Related Topics 数学 二分查找 👍 209 👎 0


/**
 * @author GodChin
 * @date 2021-11-30 09:29:41
 * @title 第 N 位数字
 * @blog https://itdfq.com
 */
class T400_NthDigit {
    public static void main(String[] args) {
        Solution solution = new T400_NthDigit().new Solution();
        int nthDigit = solution.findNthDigit(14);
        System.out.println(nthDigit);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public int findNthDigit(int n) {
            //1-9: 9位
            //10-99 : 90位
            //100-999: 900位
            //9位    ：900000000
            int cur = 1, base = 9;
            while (n > cur * base) {
                n -= cur * base;
                cur++;
                base *= 10;
                if (Integer.MAX_VALUE / base < cur) {
                    break;
                }
            }
            n--;
            int num = (int) Math.pow(10, cur - 1) + n / cur, idx = n % cur;
            return num / (int) Math.pow(10, cur - 1 - idx) % 10;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
